// 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/product-of-array-except-self
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 看了题解，双向指针

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 88.19%
// 的用户
// 内存消耗：
// 23.4 MB
// , 在所有 C++ 提交中击败了
// 78.99%
// 的用户

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<set>
#include<queue>
using namespace std;
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int begin =0,end=nums.size();
        vector<int> res(end,1);
        int left =1,right=1;
        for(int i=begin,j=end-1;i<end;i++,j--){
            res[i] = left * res[i];
            res[j] = right * res[j];
            left = left * nums[i];
            right = right*nums[j];
        }
        return res;
    }
};